﻿namespace RankDemo.WebApi.Entities
{
    public class RankBinaryTree
    {
        private TreeNode _root;
        private SortedDictionary<int, SortedSet<long>> _data;
        private long CurrentRank;

        public RankBinaryTree(int max)
        {
            _root = new TreeNode() { ValueFrom = 0, ValueTo = max + 1, Height = 1 };
            _root.LeftChildNode = CreateChildNode(_root, 0, _root.ValueTo / 2);
            _root.RightChildNode = CreateChildNode(_root, _root.ValueTo / 2, max);
            _data = new SortedDictionary<int, SortedSet<long>>();
        }

        private TreeNode CreateChildNode(TreeNode current, int min, int max)
        {
            if (min == max) return null;
            var node = new TreeNode() { ValueFrom = min, ValueTo = max, Height = current.Height + 1 };
            node.Parent = current;
            int center = (min + max) / 2;
            if (min < max - 1)
            {
                node.LeftChildNode = CreateChildNode(node, min, center);
                node.RightChildNode = CreateChildNode(node, center, max);
            }
            return node;
        }

        public void Insert(int value, long customerId)
        {
            InnerInsert(_root, value, customerId);
            if (!_data.ContainsKey(value))
            {
                _data.Add(value, new SortedSet<long>());
            }

            if (_data[value] == null)
            {
                _data[value] = new SortedSet<long>();
            }

            if (!_data[value].Any(c => c == customerId))
            {
                _data[value].Add(customerId);
            }
        }

        private void InnerInsert(TreeNode node, int value, long customerId)
        {
            if (node == null) return;

            if (value >= node.ValueFrom && value < node.ValueTo)
            {
                node.Count++;
                InnerInsert(node.LeftChildNode, value, customerId);
                InnerInsert(node.RightChildNode, value, customerId);
            }
        }

        public void Update(int originValue, int newValue, long customerId)
        {
            Remove(originValue, customerId);
            Insert(newValue, customerId);
        }

        public void Remove(int value, long customerId)
        {
            if (!_data[value].Remove(customerId)) return;
            InnerRemove(_root, value);
        }

        public void InnerRemove(TreeNode node, int value)
        {
            if (node == null) return;

            if (value >= node.ValueFrom && value < node.ValueTo)
            {
                node.Count--;
                InnerRemove(node.LeftChildNode, value);
                InnerRemove(node.RightChildNode, value);
            }
        }

        public int GetRank(int value)
        {
            if (value < 0) return 0;
            return InnerGet(_root, value);
        }

        private int InnerGet(TreeNode node, int value)
        {
            if (node.LeftChildNode == null || node.RightChildNode == null) return 1;
            if (value >= node.LeftChildNode.ValueFrom && value < node.LeftChildNode.ValueTo)
            {
                return node.RightChildNode.Count + InnerGet(node.LeftChildNode, value);
            }
            else
            {
                return InnerGet(node.RightChildNode, value);
            }
        }

        public List<Leaderboard> GetAllLeaf()
        {
            var leaderboards = new List<Leaderboard>();
            InnerGet(_root, leaderboards);
            return leaderboards;
        }

        private void InnerGet(TreeNode node, List<Leaderboard> leaderboards)
        {
            if (node == null) return;

            if (node.Count <= 0) return;

            InnerGet(node.RightChildNode, leaderboards);
            InnerGet(node.LeftChildNode, leaderboards);

            if (node.RightChildNode == null && node.LeftChildNode == null)//Leaf
            {
                long index = CurrentRank;

                foreach (var leafData in _data[node.ValueFrom])
                {
                    index++;

                    leaderboards.Add(new Leaderboard()
                    {
                        CustomerId = leafData,
                        Score = node.ValueFrom,
                        Rank = index
                    });
                }

                CurrentRank += node.Count;
            }
        }

        public bool ContainValue(int value)
        {
            return _data.ContainsKey(value);
        }
    }

    public class TreeNode
    {
        public int ValueFrom { get; set; }

        public int ValueTo { get; set; }

        public int Count { get; set; }

        public int Height { get; set; }

        public TreeNode Parent { get; set; }

        public TreeNode LeftChildNode { get; set; }

        public TreeNode RightChildNode { get; set; }
    }
}